//题目:
// 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
// 在选修某些课程之前需要一些先修课程。 
// 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
// 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
// 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<vector>

using namespace std;
//代码:
class Solution 
{
public:
    // bool canFinish(int numCourses, vector<vector<int>>& p) 
    // {
    //     //1.用一个哈希表来存放p中课程和先修课程的关系
    //     unordered_multimap<int,int> hash_p;
    //     for(int i=0;i<p.size();i++)
    //         hash_p.insert(make_pair(p[i][0],p[i][1]));

    //     //2.找到入度为0的所有顶点,hash.second==0对应的first的顶点就是入度为0的点
    //     unordered_map<int,int> hash;//key表示课程标号,value表示对应课程的先修课程门数(入度)
    //     for(int i=0;i<numCourses;i++)hash[i]=0;
    //     for(int i=0;i<p.size();i++)hash[p[i][1]]++;

    //     //3.将所有入度为0的顶点入队列
    //     queue<pair<int,int>> q;
    //     for(const auto& pir:hash) 
    //     {
    //         if(pir.second==0 && hash_p.count(pir.first)) 
    //         {
    //             for(const auto& hsh:hash_p)
    //                 if(hsh.first==pir.first)
    //                     q.push(make_pair(pir.first,hsh.second));
    //         }
    //     }

    //     //4.用bfs进行拓扑排序,并将排序的结果存放在一个容器中
    //     vector<pair<int,int>> v;
    //     while(!q.empty())
    //     {
    //         //a.拿出顶点
    //         pair<int,int> pir=q.front();
    //         q.pop();

    //         //b.去除连线，同时判断是否入队列
    //         if(--hash[pir.second]==0 && hash_p.count(pir.second))
    //         {
    //             for(const auto& hsh:hash_p)
    //                 if(hsh.first==pir.second)
    //                     q.push(make_pair(pir.second,hsh.second));
    //         }

    //         //c.将顶点放入存放拓扑排序结果的容器中
    //         v.push_back(pir);
    //     }

    //     //5.返回结果
    //     return v.size()==p.size()?true:false;
    // }

    //优化后：
    // bool canFinish(int numCourses, vector<vector<int>>& p) 
    // {
    //     //1.用一个哈希表来存放p中课程和先修课程的关系
    //     unordered_map<int,vector<int>> hash_p;//key是课程，value是先修课程，如果存在一个key对应多个value的情况，可以用<int,vector<int>>来解决
    //     for(int i=0;i<p.size();i++)
    //         hash_p[p[i][0]].push_back(p[i][1]);

    //     //2.找到入度为0的所有顶点
    //     unordered_map<int,int> hash;//key表示课程标号,value表示对应课程的先修课程门数(入度)
    //     for(int i=0;i<numCourses;i++)hash[i]=0;//初始化
    //     for(int i=0;i<p.size();i++)hash[p[i][1]]++;//*核心步骤:p[i][0]——>p[i][1]  所以p[i][1]++  

    //     //3.将所有入度为0的顶点入队列
    //     queue<pair<int,int>> q;
    //     for(const auto& pir:hash) 
    //     {
    //         if(pir.second==0 && hash_p.count(pir.first))//pir.second就是pir.first的入度
    //         {
    //             for(const auto& x:hash_p[pir.first])
    //                 q.push(make_pair(pir.first,x));
    //         }
    //     }

    //     //4.用bfs进行拓扑排序,并将排序的结果存放在一个容器中
    //     vector<pair<int,int>> v;
    //     while(!q.empty())
    //     {
    //         //a.拿出顶点
    //         pair<int,int> pir=q.front();
    //         q.pop();

    //         //b.去除连线，同时判断是否入队列
    //         if(--hash[pir.second]==0 && hash_p.count(pir.second))
    //         {
    //             for(const auto& x:hash_p[pir.second])
    //                 q.push(make_pair(pir.second,x));
    //         }

    //         //c.将顶点放入存放拓扑排序结果的容器中
    //         v.push_back(pir);
    //     }

    //     //5.返回结果
    //     return v.size()==p.size()?true:false;
    // }

    //终极优化后:
    bool canFinish(int numCourses, vector<vector<int>>& p) 
    {
        //1.用一个哈希表来存放p中课程和先修课程的关系
        unordered_map<int,vector<int>> hash_p;//key是课程，value是先修课程，如果存在一个key对应多个value的情况，可以用<int,vector<int>>来解决
        for(int i=0;i<p.size();i++)
            hash_p[p[i][1]].push_back(p[i][0]);//p[i][1]——>p[i][0]

        //2.找到入度为0的所有顶点
        unordered_map<int,int> hash;//key表示课程标号,value表示对应课程的先修课程门数(入度)
        for(int i=0;i<numCourses;i++)hash[i]=0;//初始化
        for(int i=0;i<p.size();i++)hash[p[i][0]]++;//*核心步骤:p[i][1]——>p[i][0]  所以p[i][0]++  

        //3.将所有入度为0的课程入队列
        queue<int> q;
        for(const auto& pir:hash) if(pir.second==0) q.push(pir.first);//pir.second就是pir.first的入度

        //4.用bfs进行拓扑排序,并将排序的结果存放在一个容器中
        vector<int> v;
        while(!q.empty())
        {
            //a.拿出顶点
            int course=q.front();q.pop();

            //b.去除连线，同时判断课程是否入队列
            for(auto& x:hash_p[course]) if(--hash[x]==0) q.push(x);
                
            //c.将顶点放入存放拓扑排序结果的容器中
            v.push_back(course);
        }

        //5.返回结果
        return v.size()==numCourses?true:false;
    }
};